[Coding021] Sort - 交换排序

快速排序

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：快速排序

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），是一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序$n$$n$个项目要${\displaystyle O(n\log n)}$${\displaystyle \ O(n\log n)}$（大O符号）次比较。在最坏状况下则需要${\displaystyle O(n^2)}$${\displaystyle O(n^{2})}$次比较，但这种状况并不常见。事实上，快速排序${\displaystyle \mathrm{\Theta }(n\log n)}$${\displaystyle \Theta (n\log n)}$通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。

——维基百科

快排思想

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），

2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，

3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

Words & phrases

pivot 美/ ˈpɪvət /

• n.支点，枢轴；最重要的人（或事物），核心；转动，旋转；策应位置；<美>中锋

• v.（使）在枢轴上旋转；（以脚为支点）转身；（为机械装置）提供枢轴

The wheels pivot for easy manoeuvring.

这些轮子绕轴转动，以方便操控。

一次完整的手工图

测试样例：11 9 10 8 13 15 7 4 19 20 8 19

※ 特殊情况（需要注意）

Java语言代码实现

x
104
1
import java.util.Scanner;
2

3
// 这是一个类，名叫Solution
4
public class Solution {
5
    /**
6
     * 快速排序(Quick Sort)
7
     */
8
    public static void main(String[] args) {
9
        // TODO Auto-generated method stub
10
        System.out.println("hello, my t!");
11

12
        Scanner input = new Scanner(System.in);
13

14
        int n = input.nextInt();
15

16
        int[] arr = new int[n];
17
        for (int i = 0; i < n; i++) 
18
        {
19
            arr[i] = input.nextInt();
20
        }
21

22
        for (int e : arr) 
23
        {
24
            System.out.print(e + " ");
25
        }
26
        System.out.println("\n--------------");
27

28
        Solution sol = new Solution();
29
        sol.QuickSort(arr, 0, arr.length - 1);
30

31
        for (int e : arr) 
32
        {
33
            System.out.print(e + " ");
34
        }
35
        return;
36
    }
37

38
    public void QuickSort(int[] arr, int i, int j) 
39
    {
40
        // 递归程序，务必要有出口！
41
        if (i >= j)
42
            return;
43

44
        int flag = Partition(arr, i, j);
45
        System.out.println("flag = " + flag);
46
        
47
        QuickSort(arr, i, flag - 1);
48
        QuickSort(arr, flag + 1, j);
49

50
        return;
51
    }
52

53
    public void swap(int[] arr, int i, int j) 
54
    {
55
        int temp = arr[i];
56
        arr[i] = arr[j];
57
        arr[j] = temp;
58
    }
59

60
    public int Partition(int[] arr, int i, int j) 
61
    {
62

63
        int flag = i;
64

65
        i = i + 1;
66

67
        while (true) 
68
        {
69
            // 条件(i < j), 防止对于类似(60 10 20 30)这样的序列中i加过头了
70
            while (arr[i] < arr[flag] && i < j) 
71
                i++;
72

73
            // 同理(j > flag), 防止对于类似(10 20 30 40)这样的序列中j减过头了
74
            while (arr[j] > arr[flag] && j > flag) 
75
                j--;
76

77
            if (i < j) {
78
                swap(arr, i, j);
79
            } 
80
            else 
81
            {
82
                swap(arr, flag, j);
83
                break;
84
            }
85
        }
86

87
        return j;
88
    }
89

90
}
91

92
/*
93
 * 测试样例: 
94
5 
95
5 4 7 9 6
96

97
9 
98
65 70 75 80 85 60 55 50 45
99

100
10 
101
10 20 30 40 50 60 70 80 90 100
102

103
20 
104
12 54 63 54 87 52 49 32 65 48 90 27 30 65 3 9 6 14 18 0
105
*/

运行结果

重点代码段解读

① 程序调用关系

② 重点代码实现

复杂度

C语言代码实现

x
1
/*
2
    快速排序 
3
*/ 
4
#include<stdio.h>
5

6
// 两个疑惑：
7
// 1. 快排是稳定排序吗？
8
// 2. 快排的其他形式代码？ （一个递归程序搞定）
9
// 3. 快排的加强版 -- suda program 
10

11
void swap(int* array, int i, int j)
12
{
13
    int temp = array[i];
14
    array[i] = array[j];
15
    array[j] = temp;
16
}
17

18
// Quick Sort
19
int partition(int* array, int s, int e)
20
{
21
    int pivot = s;
22
    // array[s, s+1, ... ,   e]
23
    // pivot = s;
24
    // i = s+1;
25
    // j = e
26
    
27
    int i = s + 1; 
28
    int j = e;
29
    
30
    while(1)
31
    {
32
        // 在一个array里，务必要有i < j的条件，不然的话，i会一直递增，超越当前范围 
33
        while(array[i] < array[pivot] && i < j)
34
        {
35
            i++;
36
        }
37
        // 在一个array里，务必要有j > pivot的条件，作为j的递减条件，不然的话，它必定会超越当前范围 
38
        while(array[j] > array[pivot] && j > pivot)
39
        {
40
            j--;
41
        }
42
        
43
        // 交换位置 
44
        if(i < j)
45
        {
46
            swap(array, i, j);
47
        }
48
        else
49
        {        
50
            // 找到了pivot的命中归属的那个位置 -> j
51
            swap(array, j, pivot);
52
            break;
53
        }
54
    }
55
    return j;
56
}
57

58
void QuickSort(int* array, int s, int e)
59
{
60
    // 递归程序，务必要有出口 
61
    if(s >= e) return;
62
    
63
    // mid位置是分割点，pivot的最终位置 
64
    int mid = partition(array, s, e);
65

66
    // system("pause");
67
    // 递归调用 
68
    QuickSort(array, s, mid - 1);
69
    QuickSort(array, mid + 1, e);
70
}
71

72
int main()
73
{
74
    int array[100];
75
    
76
    int cnt;
77
    int i;
78
    
79
    scanf("%d", &cnt);
80
    for(i = 0; i < cnt; i++)
81
    {
82
        scanf("%d", &array[i]);
83
    }
84

85
    QuickSort(array, 0, cnt-1);
86
    
87
    for(i = 0; i < cnt; i++)
88
    {
89
        printf("%d ", array[i]);
90
    }
91
}
92

93

94
/* test case 1:
95

96
9
97
11 20 9 6 8 19 5 17 3
98

99
11 
100
9 10 8 13 15 7 4 19 20 8 19
101

102
*/

运行结果

C++语言代码实现

xxxxxxxxxx
1
107
1
#include<iostream>
2
using namespace std;
3

4
#define INF 10000000;
5
int n;
6
int A[100001];
7

8
void Interchange(int* a, int* b)
9
{
10
    int temp;
11
    temp = *a;
12
    *a = *b;
13
    *b = temp;
14
}
15

16
int Partition(int m, int j)
17
{
18
    int i;
19
    int v;
20
    v = A[m];
21
    i = m;    
22
    while(1)
23
    {
24
        do
25
        {
26
            i = i + 1;            
27
        }while(A[i] < v);
28
        
29
        do
30
        {
31
            j = j - 1;
32
        }while(A[j] > v);
33
        
34
        if (i < j)
35
        {
36
            Interchange(&A[i], &A[j]);
37
        }
38
        else
39
        {
40
            break;
41
        }
42
    }    
43
    
44
    A[m] = A[j];
45
    A[j] = v;
46
    
47
    /*
48
    cout<<"##############################################"<<endl;
49
    for(int ii = m; ii <= j; ii++)
50
    {
51
        cout<<A[ii]<<" ";
52
    }
53
    cout<<endl;
54
    cout<<"##############################################"<<endl;
55
    system("pause");
56
    */
57
    
58
    return j;
59
}
60
void QuickSort(int p, int q)
61
{
62
    int j;
63
    if (p < q)
64
    {
65
        j = q + 1;
66
        j = Partition(p, j);
67
        
68
        // cout<<"----->>>>> p:"<<p<<"\t"<<"j:"<<j<<endl;
69
        QuickSort(p, j - 1);
70
        QuickSort(j + 1, q);
71
    }    
72
}
73
int main()
74
{
75
    int i;
76
    cout<<"Please input the number of the Array ->N:";
77
    cin>>n;
78
    cout<<"Please input "<<n<<" numbers in the below:"<<endl;
79
    for(i = 1; i <= n; i++)
80
    {
81
        cin>>A[i];
82
    }
83
    A[n + 1] = INF;
84
    QuickSort(1, n);
85
    cout<<"After QuickSort:"<<endl;
86
    for(i = 1; i <= n; i++)
87
    {
88
        cout<<A[i]<<" ";
89
    }
90
    cout<<endl;
91
    return 0;
92
}
93
/*
94
5
95
5 4 7 9 6
96

97
9
98
65 70 75 80 85 60 55 50 45
99

100
10
101
10 20 30 40 50 60 70 80 90 100
102

103
20
104
12 54 63 54 87 52 49 32 65 48 90 27 30 65 3 9 6 14 18 0
105

106
*/

运行结果